package com.winning.sort;


/**
 * @author Hao.Y
 * 排序算法
 */
public class TestSort {


    public static void main(String[] args) {
        int[] a = {4,49,24,56,89,22,54,87,1};
        sort(a, 0, a.length-1);
        print(a);
    }


    /**
     * 插入排序
     * 复杂度 o(n2)
     * @param a
     * @return
     */
    private static void insertion_sort(int[] a){

        if(a == null || a.length == 0){
            throw new RuntimeException("数组没有数据");
        }

        int v,j;
        for (int i = 0; i < a.length; i++) {
            for(v=a[i],j=i-1; j>=0 && a[j]<v; j--){
                a[j+1] = a[j];
            }

            a[j+1] = v;
            print(a);
        }
    }

    /**
     * 选择排序
     * 复杂度 o(n2)
     * @param a
     * @return
     */
    private static void selection_sort(int[] a){
        if(a == null || a.length == 0){
            throw new RuntimeException("数组没有数据");
        }

        int j,pos,tmp;
        int size = a.length;
        for (int i = 0; i < size - 1; i++) {

            //寻找最小值的下表
            for (pos = i, j=i+1; j<size; j++){
                if(a[pos] > a[j]){
                    pos = j;
                }
            }
            if(pos != i){
                tmp = a[i];
                a[i] = a[pos];
                a[pos] = tmp;
            }

           print(a);
        }
    }


    /**
     * 冒泡排序
     * 复杂度o(n2)
     * @param a
     * @return
     */
    private static void bubble_sort(int[] a){
        int tmp;
        for(int i =0; i<a.length-1; i++){
            for(int j=i+1; j<a.length; j++){

                if(a[i] > a[j]){
                    tmp = a[j];
                    a[j] = a[i];
                    a[i] = tmp;
                }
            }

            print(a);
        }
    }

    /**
     * 快速排序
     * @param a
     * @return
     */
    private static int quick_sort(int[] a, int low, int high){

        int key = a[low];

        while (high > low){

            while (a[high] >= key && high>low){
                high --;
            }

            a[low] = a[high];
            System.out.println(low + " : " + high);
            print(a);

            while ((a[low] <= key && high>low)){
                low ++;
            }
            System.out.println(low + " : " + high);
            a[high] = a[low];

            print(a);
        }

        a[high] = key;
        return high;
    }

    public static void sort(int[] array,int lo ,int hi){
        if(lo>=hi){
            return ;
        }
        int index=quick_sort(array,lo,hi);
        sort(array,lo,index-1);
        sort(array,index+1,hi);
    }

    private static void print(int[] a){
        for(int item : a){
            System.out.print(item + " ");
        }
        System.out.println();
    }

}
